// QuickSort 快速排序
// 实际情况下最实用的排序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 打印数组
void PrintArray(int* arr, int n)
{
    for (int i = 0 ; i < n ; i++){
        printf("%d ", arr[i]);
    }
    putchar('\n');
}

// 交换函数
void Swap(int* pnum1, int* pnum2)
{
    int tmp = *pnum1;
    *pnum1 = *pnum2;
    *pnum2 = tmp;
}

// 快速排序最坏情况是有序，所以采用三数取中的方法来规避这个问题
// 三数取中保证了不会到最坏情况
int GetMidIndex(const int* arr, int left, int right)
{
    int mid = (left + right) >> 1; // 二进制向右移动一位

    if (arr[left] < arr[mid]){
        if (arr[mid] < arr[right]){
            return mid;
        }
        else if (arr[left] > arr[right]){
            return left;
        }
        else {
            return right;
        }
    }
    else { // arr[left]>arr[mid]
        if (arr[mid] > arr[right]){
            return mid;
        }
        else if (arr[left] < arr[right]){
            return left;
        }
        else {
            return right;
        }
    }
}

// 挖坑法
// 一般key选第一个或者最后一个
// 可以采用小区间优化
void QuickSort(int* arr, int left, int right)
{
    if (left >= right){
        return ;
    }

    int index = GetMidIndex(arr, left, right);
    Swap(&arr[index], &arr[left]);

    int begin = left, end = right;
    int pivot = begin;
    int key = arr[begin];

    while (begin < end){
        // 右边找小，放到左边
        while (begin < end && arr[end] >= key){
            end--;
        }

        // 小的放到左边的坑里，自己形成新的坑位
        arr[pivot] = arr[end];
        pivot = end;

        // 左边找大
        while (begin < end && arr[begin] <= key){
            begin++;
        }

        // 大的放到左边的坑里，自己形成新的坑位
        arr[pivot] = arr[begin];
        pivot = begin;
    }

    pivot = begin;
    arr[pivot] = key;

    QuickSort(arr, left, pivot - 1);
    QuickSort(arr, pivot + 1, right);
}

/*
int Partition(int* arr, int left, int right)
{
    int begin = left, end = right;
    int key = arr[left];

    while (begin < end){
        // 找小
        // 不加等于，若左右指针指向同一个值，会陷入死循环
        while (begin < end && arr[end] >= key){ // 等于是必要的，不然可能会陷入死循环
            end--;
        }

        // 找大
        while (begin < end && arr[begin] <= key){
            begin++;
        }

        Swap(&arr[begin], &arr[end]);
    }

    Swap(&arr[begin], &arr[left]);
    return begin;
}

void QuickSort(int* arr, int left, int right){
    if (left >= right){
        return ;
    }

    int KeyIndex = Partition(arr, left, right);
    QuickSort(arr, left, KeyIndex - 1);
    QuickSort(arr, KeyIndex + 1, right);
}
*/

/*
// 前后指针法
// cur找小
// 每次cur找到比key小的就prev++
// 交换prev和cur的数值
int Partition(int* arr, int left, int right)
{
    int key = left;
    int prev = left, cur = left + 1;

    while (cur <= right){
        if (arr[cur] < arr[key] && ++prev != cur){
            Swap(&arr[cur], &arr[prev]);
        }
        cur++;
    }

    Swap(&arr[prev], &arr[key]);
    return prev;
}

void QuickSort(int* arr, int left, int right)
{
    if (left >= right){
        return ;
    }
    int index = Partition(arr, left, right);

    QuickSort(arr, left, index - 1);
    QuickSort(arr, index + 1, right);
}
*/

//int main(void)
//{
//    int arr[] = {0, 5, 6, 4, 8, 9};
//
//    QuickSort(arr, 0, 5);
//    PrintArray(arr, 6);
//
//    return 0;
//}
//
//typedef int STDataType;
//typedef struct Stack
//{
//    STDataType *data;
//    int top;
//    int capacity;
//}Stack;
//
//// 函数接口一览
//void StackInit(Stack* ps);
//void StackDestroy(Stack* ps);
//
//void StackPush(Stack* ps, STDataType val);
//void StackPop(Stack* ps);
//
//STDataType StackTop(Stack* ps);
//bool isStackEmpty(Stack* ps);
//
//void Swap(int* pnum1, int* pnum2);
//void PrintArray(int* arr, int n);
//
//int Partition(int* arr, int left, int right);
//void QuickSortNonR(int* arr, int n); // n为数组的大小
//
//int main(void)
//{
//    int arr[] = {0, 5, 6, 2, 8, 9, 5, 3, 4};
//
//    QuickSortNonR(arr, sizeof(arr) / sizeof(int));
//    PrintArray(arr, sizeof(arr) / sizeof(int));
//    return 0;
//}
//
//// 接口实现
//void StackInit(Stack* ps)
//{
//    assert(ps);
//
//    ps->data = (STDataType*)malloc(sizeof(STDataType) * 4);
//    if (ps->data == NULL){
//        printf("malloc fail\n");
//        exit(-1);
//    }
//
//    ps->capacity = 4;
//    ps->top = 0;
//}
//
//void StackDestroy(Stack* ps)
//{
//    assert(ps);
//
//    free(ps->data);
//    ps->data = NULL;
//    ps->top = ps->capacity = 0;
//}
//
//void StackPush(Stack* ps, STDataType val)
//{
//    assert(ps);
//
//    if (ps->top == ps->capacity){
//        STDataType* tmp = (STDataType*)realloc(ps->data, ps->capacity * 2 * sizeof(STDataType));
//        if (tmp == NULL){
//            printf("realloc fail\n");
//            exit(-1);
//        }
//        else {
//            ps->data = tmp;
//            ps->capacity *= 2;
//        }
//    }
//
//    ps->data[ps->top] = val;
//    ps->top++;
//}
//
//void StackPop(Stack* ps)
//{
//    assert(ps);
//    assert(ps->top > 0); // 栈空时报错
//
//    ps->top--;
//}
//
//STDataType StackTop(Stack* ps)
//{
//    assert(ps);
//    assert(ps->top > 0); // 栈空时报错
//
//    return ps->data[ps->top - 1];
//}
//
//bool isStackEmpty(Stack* ps)
//{
//    assert(ps);
//
//    return ps->top == 0;
//}
//
//void Swap(int* pnum1, int* pnum2)
//{
//    int tmp = *pnum1;
//    *pnum1 = *pnum2;
//    *pnum2 = tmp;
//}
//
//int Partition(int* arr, int left, int right)
//{
//    int begin = left, end = right;
//    int key = arr[left];
//
//    while (begin < end){
//        // 找小
//        while (begin < end && arr[end] >= key){ // 等于是必要的，不然可能会陷入死循环
//            end--;
//        }
//
//        // 找大
//        while (begin < end && arr[begin] <= key){
//            begin++;
//        }
//
//        Swap(&arr[begin], &arr[end]);
//    }
//
//    Swap(&arr[begin], &arr[left]);
//    return begin;
//}
//
//void PrintArray(int* arr, int n)
//{
//    for (int i = 0 ; i < n ; i++){
//        printf("%d ", arr[i]);
//    }
//    putchar('\n');
//}
//
//void QuickSortNonR(int* arr, int n)
//{
//    // 初始化
//    Stack st;
//    StackInit(&st);
//
//    // 先把最开始的两边界入栈
//    StackPush(&st, n - 1);
//    StackPush(&st, 0);
//
//    // 进入循环，结束条件为空栈
//    while (!isStackEmpty(&st)){
//        int left = StackTop(&st);
//        StackPop(&st);
//
//        int right = StackTop(&st);
//        StackPop(&st);
//
//        int key = Partition(arr, left, right);
//
//        // 先排左边，因此先让右边界进栈
//        if (key + 1 < right){
//            StackPush(&st, right);
//            StackPush(&st, key + 1);
//        }
//
//        if (left < key - 1){
//            StackPush(&st, key - 1);
//            StackPush(&st, left);
//        }
//    }
//
//    StackDestroy(&st);
//}

// 递归的缺陷：递归会建立栈帧，可能会造成栈溢出
// 递归改非递归，有两种方法：
// 1.直接改循环
// 2.利用数据结构栈

//#include <stdio.h>
//#include <stdlib.h>
//
//void PrintArray(int* arr, int n)
//{
//    for (int i = 0 ; i < n ; i++){
//        printf("%d ", arr[i]);
//    }
//    putchar('\n');
//}
//
//void MergeSortNonR(int* arr, int n)
//{
//    int* tmp = (int*)malloc(sizeof(int) * n);
//    int gap = 1;
//
//    while (gap < n){
//        for (int i = 0 ; i < n ; i += 2 * gap){
//            // 拆成[i, i+gap-1],[i+gap, i+2*gap-1]两个区间
//            int begin1 = i, end1 = i + gap - 1;
//            int begin2 = i + gap, end2 = i + 2 * gap - 1;
//
//            // 没有右区间
//            if (begin2 >= n){
//                break;
//            }
//
//            // 右区间过长
//            if (end2 >= n){
//                end2 = n - 1;
//            }
//
//            // 归并
//            int index = begin1; // index是tmp的下标
//            while (begin1 <= end1 && begin2 <= end2){
//                if (arr[begin1] < arr[begin2]){
//                    tmp[index++] = arr[begin1++];
//                }
//
//                else {
//                    tmp[index++] = arr[begin2++];
//                }
//            }
//
//            while (begin1 <= end1){
//                tmp[index++] = arr[begin1++];
//            }
//
//            while (begin2 <= end2){
//                tmp[index++] = arr[begin2++];
//            }
//
//            // 拷贝
//            for (int j = i ; j <= end2 ; j++){
//                arr[j] = tmp[j];
//            }
//
//        }
//        gap *= 2;
//    }
//    free(tmp);
//}
//
//int main(void)
//{
//    int arr[] = {1, 5, 9, 6, 7, 3, 1};
//
//    MergeSortNonR(arr, sizeof(arr) / sizeof(int));
//    PrintArray(arr, sizeof(arr) / sizeof(int));
//
//    return 0;
//}
//
//
//





























